A Note on Multiparty Communication Complexity and the Hales-Jewett Theorem

摘要

For integers $n$ and $k$, the density Hales-Jewett number $c_{n,k}$ isdefined as the maximal size of a subset of $[k]^n$ that contains nocombinatorial line. We prove a lower bound on $c_{n,k}$, similar to the lowerbound in \cite{polymath2010moser}, but with better dependency on $k$. The boundin \cite{polymath2010moser} is roughly $c_{n,k}/k^n \ge exp(-O(\logn)^{1/\lceil \log_2 k\rceil})$ and we show $c_{n,k}/k^n \ge exp(-O(\logn)^{1/(k-1)})$. The proof of the bound uses the well-known construction ofBehrend \cite{behrend1946sets} and Rankin \cite{rankin1965sets}, as the one in\cite{polymath2010moser}, but does not require the recent refinements\cite{elkin2010improved, green2010note, o2011sets}. Instead our proof relies onan argument from communication complexity. In addition, we show that for $k \ge 3$ the density Hales-Jewett number$c_{n,k}$ is equal to the maximal size of a cylinder intersection in theproblem $Part_{n,k}$ of testing whether $k$ subsets of $[n]$ form a partition.It follows that the communication complexity, in the Number On the Forehead(NOF) model, of $Part_{n,k}$, is equal to the minimal size of a partition of$[k]^n$ into subsets that do not contain a combinatorial line. Thus, Tesson'sbound on the problem using the Hales-Jewett theorem \cite{tessonapplication} isin fact tight, and the density Hales-Jewett number can be thought of as aquantity in communication complexity.